This section is intended to introduce various aspects of the art, which may be associated with exemplary embodiments of the present techniques. This discussion is believed to assist in providing a framework to facilitate a better understanding of particular aspects of the present techniques. Accordingly, it should be understood that this section should be read in this light, and not necessarily as admissions of prior art.
Modern society is greatly dependant on the use of hydrocarbons for fuels and chemical feedstocks. Hydrocarbons are generally found in subsurface rock formations that can be termed “reservoirs.” Removing hydrocarbons from the reservoirs depends on numerous physical properties of the rock formations, such as the permeability of the rock containing the hydrocarbons, the ability of the hydrocarbons to flow through the rock formations, and the proportion of hydrocarbons present, among others.
Often, mathematical models termed “simulation models” are used to simulate hydrocarbon reservoirs and optimize the production of the hydrocarbons. A simulation model is a type of computational fluid dynamics simulation where a set of partial differential equations (PDE's) which govern multi-phase, multi-component fluid flow through porous media and the connected facility network is approximated and solved. This is an iterative, time-stepping process where a particular hydrocarbon production strategy is optimized.
Simulation models discretize the underlying PDEs on a structured (or unstructured) grid, which represents the reservoir rock, wells, and surface facility network. State variables, such as pressure and saturation, are defined at each grid block. The goal of a simulation model is generally to understand the flow patterns of the underlying geology in order to optimize the production of hydrocarbons from a set of wells and surface facilities. During the past five decades, the size and complexity of simulation models have grown proportionally with the increased availability of computing capacity. Complex simulation models often require the use of parallel computing systems and algorithms to provide adequate simulation turnaround time.
Accordingly, a simulation model can be divided into a number of subsections, or subdomains, wherein each subdomain may be assigned or partitioned to a different computing unit, such as a processor in a cluster computing system or a computing core in a multi-core desktop. However, poor partitioning may result in slow convergence to a solution or even in a failure of the model to converge to a solution. For example, if a partition of a simulation model between different computing units crosses a production well, the simulation may fail. Generally, partitioning may be performed by a mathematical analysis of a graph representing the simulation model.
Recently, there have been a number of research articles published on the general subject of graph partitioning, for example, as applied to finite element analysis and other problems. See, for example, J. D. Teresco, K. D. Devine, and J. E. Flaherty, “Partitioning and Dynamic Load Balancing for the Numerical Solution of Partial Differential Equations,” Numerical Solution of Partial Differential Equations on Parallel Computers, Chapter 2, 55-88 (Springer, N.Y., 2006); and B. Hendrickson and T. Kolda, “Graph Partitioning Models for Parallel Computing,” Parallel Computing, 26, 1519-1534 (2000). Some of the partitioning techniques have been implemented in software, such as the METIS program. See G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on Scientific Computing, 20, 359-392 (1999). Another example is the Chaco program, developed at Sandia National Laboratory. See B. Hendrickson and R. Leland, “An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations,” SIAM Journal on Scientific and Statistical Computing, 16, 452-469 (1995); see also B. Hendrickson and R. Leland, “The Chaco User's Guide: Version 2.0,” Sandia Tech Report SAND94-2692 (1994).
The graph partitioning algorithms are organized into two main classes: global and multi-level. The global algorithms take as input a global graph, or map of the simulation, and perform a spectral technique (such as an eigenvalue decomposition of a Laplacian representation of the global graph) to generate the partitions. These algorithms produce good quality partitions, but are computationally expensive for large problems. Both Chaco and METIS have global algorithms implemented in each software package.
In contrast, multi-level algorithms take the global graph as an input, but create a sequence of coarser, or less detailed, graphs until a certain threshold is reached. The coarsest graph is partitioned using a local optimization technique, such as a spectral technique. The partition on the coarsest level is projected back to finer levels, thus creating a partition for the entire grid. For large graphs, multi-level techniques are preferable due to faster computational time than the global techniques.
Software packages that implement partitioning algorithms generally allow the user to assign a weight to the connection associated with each graph node. For most algorithms, the weights are positive integers. The integer values of the weights should have a relatively short range, such as from about 1 to about 1000 or about 10,000. As the range increases, the robustness of a partitioning algorithm and the quality of a created partition deteriorates. Moreover, the published algorithms and software do not include methods for keeping certain grid blocks or physical properties of a model together in one subdomain. In other words, when using publicly available software, such as METIS or Chaco it is impossible to ensure that certain graph connections are preserved resulting in the corresponding nodes being partitioned into separate subdomains by the partitioning algorithm.
There are approaches to assign the real weight values to edges and nodes of the graph to improve the quality of the partition. Some of them, pertinent to problems in the oil and gas industry are described in International Patent Publication No. WO2009/075945. The patent describes how to construct real weights for nodes and/or connections based on physical information (for example, transmissibility, flux values, etc). Unfortunately, there is not a robust algorithm to map real weights with a very large range to a short range of integer values, in order to produce a robust partition for simulation models.